package class05_06_mergeSortRelated;

/*
* https://leetcode.cn/problems/count-of-range-sum/
* 方法必须 N*log(N)才能通过
* 1、累加和 sum[i...j] = sum[0...j]-sum[0...i]
* 2、先判断 sum[0...j]是否符合要求，再判断子列[i...j](在merge过程中判断)
* 3、左列右列分开，对一个特定的右列数，找满足要求的左列数（左列有序，则可以不回退往前）
*    刚开始是左列1个，右列1个，所以所有的右边前缀和都会和左边的前缀和比到，只不过因为有序，所以其中一些比较隐式地通过单调的结构省略了
* 4、然后merge成一个有序的整体，用于下一次寻找
* 5、利用了有序数列的单调性，节省了比较的时间
* */

public class RangeSumCounter {
    public static int countRangeSum(int[] nums, int lower, int upper) {
        //    long[] preSum = new long[nums.length];
        //    preSum[0]=nums[0];
        //    for (int i = 1; i<nums.length; i++){
        //        preSum[i]=preSum[i-1]+nums[i];
        //    }

        //     int count = 0;
        //     for(int i = nums.length-1; i>=0; i--){
        //         if(preSum[i]<=upper && preSum[i]>=lower) count++;
        //         for (int j=0;j<i;j++){
        //             long preSumDif = preSum[i]-preSum[j];
        //             long difLower = preSum[i]-upper;
        //             long difUpper = preSum[i]-lower;
        //             if(preSum[j]>=difLower && preSum[j]<=difUpper) count++;
        //         }
        //     }
        int count = mergeSortGetRangeSum(nums,lower,upper);
        return count;
    }

    public static int mergeSortGetRangeSum(int[] arr, int lower, int upper){
        long[] preSum = new long[arr.length];
        //get preSum
        preSum[0]=arr[0];
        for(int i=1; i<arr.length; i++){
            preSum[i]=arr[i]+preSum[i-1];
        }

        int groupSize = 1;
        int rangeSum = 0;

        //不减去任何前缀和的情况
        for(int i = 0; i<arr.length; i++){
            if(preSum[i]<=upper && preSum[i]>=lower) rangeSum++;
        }

        while(groupSize<arr.length){
            int l = 0;
            int r = l+2*groupSize-1;
            int m = (l+r)/2;
            while(m<arr.length-1){
                if(r>arr.length-1) rangeSum += mergeAndGetRangeSum(preSum,l,m,arr.length-1,lower,upper);
                else rangeSum += mergeAndGetRangeSum(preSum,l,m,r,lower,upper);
                l = r+1;
                r = l+2*groupSize-1;
                m = (l+r)/2;
            }
            groupSize*=2;
        }
        for(int i=0;i<preSum.length;i++) System.out.print(preSum[i]+" ");
        System.out.println("");
        return rangeSum;
    }

    public static int mergeAndGetRangeSum(long[] preSum, int l, int m, int r, int lower, int upper){
        //不回退地找区间，对右列上的数找到左列上的对应值
        int rangeSum = 0;
        long preSumLower = 0;
        long preSumUpper = 0;
        int pointer2 = m+1;
        int pointer1L = l;
        int pointer1R = l;
        while(pointer2<=r){
            preSumLower = preSum[pointer2] - upper;
            preSumUpper = preSum[pointer2] - lower;
            while(pointer1L<=m && preSum[pointer1L]<preSumLower)pointer1L++;
            while(pointer1R<=m && preSum[pointer1R]<=preSumUpper)pointer1R++;
            //if(pointer1R-pointer1L>0)
            rangeSum+=(pointer1R-pointer1L);
            pointer2++;
        }

        //正常merge
        long[] temp = new long[r-l+1];
        int pointer1 = l;
        pointer2 = m+1;
        int pointerMerge = 0;

        while(pointerMerge<temp.length){
            if(pointer1>m){
                temp[pointerMerge] = preSum[pointer2++];
            } else if(pointer2>r) {
                temp[pointerMerge] = preSum[pointer1++];
            } else if(preSum[pointer1]<preSum[pointer2]){
                temp[pointerMerge] = preSum[pointer1++];
            } else {
                temp[pointerMerge] = preSum[pointer2++];
            }
            pointerMerge++;
        }

        //copy
        for (int i = 0; i<temp.length; i++){
            preSum[l+i] = temp[i];
        }

        return rangeSum;
    }

    public static void main(String[] args) {
        int[] arr = {0,0};
        System.out.println(countRangeSum(arr,0,0));
        for(int i=0;i<arr.length;i++) System.out.print(arr[i]+" ");
    }
}
